1. Field of the Invention
One embodiment of the invention relates to an overlay network system which constructs and maintains an overlay network.
2. Description of the Related Art
Recently, increasing research and development efforts have been directed toward a method of constructing and maintaining an overlay network of peer-to-peer systems (P2P systems) or toward a system using the method. As such a method, for example, Tapestry, Pastry, and Chord have particularly attracted attention.
Tapestry has been developed mainly by the University of California at Berkeley (UCB). Tapestry has been disclosed in, for example, http://p2p.cs.ucsb.edu/chimera/ (hereinafter, referred to as document 1) and Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, and John D. Kubiatowics, “Tapestry: A Resilient Global-Scale Overlay for Service Deployment,” IEEE Journal on Selected Areas in Communications, Vol 22, No. 1, 2004 (hereinafter, referred to as document 2).
Pastry has been developed mainly by Microsoft Corporation. Pastry has been disclosed in, for example, http://research.microsoft.com/˜antr/PAST/default.htm (hereinafter, referred to as document 3) and A. Rowstron and P. Druschel, “Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility,” 18th ACM SOSP' 01, Lake Louise, Alberta, Canada, 2001 (hereinafter, referred to as document 4).
Chord has been developed mainly by the Massachusetts Institute of Technology (MIT). Chord has been disclosed in, for example, http://pdos.csail.mit.edu/chord/ (hereinafter, referred to as document 5) and Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” ACM SIGCOMM 2001, 2001 (hereinafter, referred to as document 6).
These methods have common features in that they construct an overlay network using the ConsistentHashing technique. The ConsistentHashing technique is characterized by managing the proximity of identifiers (IDs) using a ring. The ConstituentHashing technique is composed of a first process and a second process described below.
1) First Process
In a first process, the hash values of the unique identifiers all the nodes and objects have are calculated using a hash function. A node is, for example, a computer. An object is, for example, a file. In the case of a node identifier, the identifier is, for example, a host name or an Internet Protocol address (IP address). In the case of an object identifier, the identifier is the name of the object or data itself. The hash value of a node identifier is referred to as a node ID. The hash value of an object identifier is referred to as an object ID.
2) Second Process
In a second process, an object is stored into a node whose node ID is closest to the object ID of the object.
In the ConsistentHashing technique, to search for a target object, an inquire may be made to search for a node whose node ID is closest to the object ID of the target object. The individual nodes constitute a distribution hash table (DHT).
There are various known methods of defining the proximity of IDs. For example, in the methods disclosed in document 5 and document 6, the hash value of the IP address of a node is defined as a node ID and the hash value of object data itself is defined as an object ID. In such methods, individual IDs are allocated to a ring which can accommodate all the IDs allowed to be used (2M IDs ranging from 0 to N=2M−1). On the ring, the proximity of two IDs is measured, depending on how far the two IDs are separated in a clockwise direction. A ring which can accommodate 2M IDs is referred to as an M-bit ring.
Hereinafter, the operation of ConsistentHashing described in document 5 and document 6 will be explained using an example. FIG. 28 shows a 3-bit ring. The circles on the ring indicate IDs. The numbers 0 to 7 written in the circles show that the corresponding IDs are ID0 to ID7 (IDs whose values range from 0 to 7). In the example of FIG. 28, an ID closest to ID0 is ID0 itself. An ID next closest to ID0 is ID1. On the other hand, an ID closest to ID7 is ID7 itself. An ID next closest to ID7 is ID0. It should be noted that the ID next closest to ID7 is not ID6.
FIG. 29 shows a state where nodes whose node IDs are {0, 3, 6} are applied to (or participate in) the 3-bit ring of FIG. 28. For the way the individual nodes constitute and maintain the ring, refer to document 5 or 6.
Here, an object whose object ID is “i” (i=1, 2, . . . , 7) is referred to as object i. A node whose node ID is “i” is referred to as node i. As shown in FIG. 29, in a state where the nodes whose node IDs are {0, 3, 6} (i.e., nodes 0, 3, and 6) have participated in the 3-bit ring, for example, object 0 is stored in node 0 to which its ID (ID=0) is closest. Similarly, object 4 is stored in node 6. In a state where nodes participate in the ring, the nodes are virtually connected to the ring.
FIG. 30 shows the range of objects each of the nodes with ID0, ID3, and ID6 (i.e., node 0, node 3, and node 6) stores in the example of FIG. 29. Here, a node whose ID is closest to a certain node ID or object ID (node/object ID) is referred to as a successor. A node whose ID is furthest from (or whose ID is closest counterclockwise to) a certain node ID or object ID is referred to as a predecessor. In the example of FIG. 30, node 6 is the successor of node 3 and the predecessor of node 0. Node 6 is also the successor of object 4 to object 6. As described above, in the method of storing objects in an overlay network using ConsistentHashing, an object is stored into a successor for the object ID of the object.
In the P2P system, an address (or the address of a storage location node) indicating the storage location of an object stored in the overlay network is not stored. For this reason, in order for an object to be taken out of the overlay network, a search on the overlay network has to be made by a multiple hop, using an object ID (or a value or a character string for generating an object ID) as an input. Therefore, in the P2P technique, a balance between the maintenance cost required for the search paths the individual nodes maintain and the search cost of how fast a target node is reached in searching is very important. The known methods of searching for an object include a broadcast method (a first method) and a full flooding method (a second method).
Let the maximum number of nodes the network can accommodate be N. In the first method, the communication cost, storage area, and time depend on value N, value N2, and value 1, as shown by O(N), O(N2), and O(1), respectively. It is known that it is necessary to monitor the participating state (participation, separation, abnormal stop) of all the nodes participating in the network.
In the second method, the communication cost, storage area, and time depend on N as shown by O(N), O(N), and O(N), respectively. It is known that the second method has a lower reliability since the full flooding does not function if a failure occurs on the path. Both the first and second method do not function if the size of the overlay network becomes large.
To overcome this problem, for example, document 5 and document 6 have proposed an algorithm for causing each node to prepare an M number of shortcut paths for searching (M=log(N)), thereby completing the reference by an M number of hops of search requests at most. Such a shortcut path is referred to as a skip table (finger table). When an object is referred to, a search request is transferred on the basis of the skip table. For the method of configuring a skip table, refer to document 5 and document 6.
In the ConsistentHashing technique as described in document 5 and document 6, the storage location of an object and the search path are determined by the “proximity” of ID. Therefore, the conventional ConsistentHashing technique has problems with “proximity” and “nonhomogeneity”.
<Proximity>
A problem with proximity is how to deal with the difference between the proximity of a P2P overlay network (logical network) and the proximity of, for example, an IP (Internet Protocol) underlay network (physical network). Another problem with proximity is what to do to take a physical network into account in determining a node for storing an object and a path for searching for an object.
<Nonhomogeneity>
A problem with nonhomogeneity is how to determine a storage location for an object, taking into account the characteristics of nodes participating in the overlay network. The characteristics of a node are variations in the capacity and performance of a disk the node has or in the capabilities, including network speed and delay.
As described above, when an overlay network is constructed, it is important to take proximity and nonhomogeneity into account. Active research and development efforts have been directed toward an overlay network. For example, Jpn. Pat. Appln. KOKAI Publication No. 2004-266796 (hereinafter, referred to as document 7) has disclosed a method of constructing an overlay network, taking proximity and nonhomogeneity into account. In the method described in document 7, a method of allocating two IDs, “name ID” and “value ID,” to a node is combined with a Plaxton algorithm.
However, in the method described in document 7, a node participating in the overlay network has to manage two IDs, its unique name ID and value ID. Moreover, in the method written in document 7, the search cost necessary for an inquiry based on the value ID varies, depending on whether a lexicographic arrangement of name IDs or an arrangement of value IDs is used.